package _10_矩形覆盖;

/**
 * 题目描述
 * 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。
 * 请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
 */

/**
 * 思路
 *      类似斐波那契数列，转化方法：
 *          n+1时，第一个小矩形竖着放时，剩下的n个就是dp[n]
 *                第一个小矩形横着放时,，剩下的方式是 dp[n-1]
 */
public class Solution {
    public int RectCover(int target) {
        if(target<1) return 0;
        if(target==1 ||target ==2) return target;
        int prepre = 1;
        int pre = 2;
        int res =0;
        for(int i=3;i<=target;i++){
            res = prepre+pre;
            prepre = pre;
            pre = res;
        }
        return res;

    }
}
